//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。 
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 
//
// 此外，你可以假设该网格的四条边均被水包围。 
//
// 
//
// 示例 1： 
//
// 
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
// 
//
// 
//
// 提示： 
//
// 
// gridLen == grid.length 
// gridWid == grid[i].length 
// 1 <= gridLen, gridWid <= 300 
// grid[i][j] 的值为 '0' 或 '1' 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 
// 👍 902 👎 0

package com.leetcode.editor.cn;

//Java：岛屿数量
class P200NumberOfIslands {
    public static void main(String[] args) {
        Solution solution = new P200NumberOfIslands().new Solution();
        // TO TEST
        char[][] grid = {{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}};
        System.out.println(solution.numIslands(grid));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int numIslands(char[][] grid) {
            //1.DFS
//            return dfs(grid);
            //2. 并查集
            int m = grid.length;
            if (m == 0) {
                return 0;
            }
            int n = grid[0].length;
            UnionFindSet uf = new UnionFindSet(grid);
            int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') { // 陆地节点
                        grid[i][j] = '0'; // 每找到一个陆地节点，将其标记为“水”
                        // 2.使用并查集对象合并四个方向上的邻接点
                        for (int[] dir : dirs) {
                            int newi = i + dir[0], newj = j + dir[1];
                            if (newi >= 0 && newi < m && newj >= 0 && newj < n && grid[newi][newj] == '1') {
                                uf.union(newi * n + newj, i * n + j);
                            }
                        }
                    }
                }
            }
            return uf.getCount();
        }

        class UnionFindSet {
            //
            int[] parent;

            int[] rank;
            int count;

            //初始化
            UnionFindSet(char[][] grid) {
                count = 0;
                int m = grid.length, n = grid[0].length;
                parent = new int[m * n];
                rank = new int[m * n];
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        int value = hash(i, j, n);
                        if (grid[i][j] == '1') {
                            parent[value] = value;
                            ++count;
                        }
                        rank[value] = 1;
                    }
                }
//                System.out.println("=========初始化=====");
//                System.out.println("parent:" + Arrays.toString(parent));
//                System.out.println("rank:" + Arrays.toString(rank));
//                System.out.println("=========初始化=====");
            }

            private int hash(int i, int j, int constant) {
                return i * constant + j;
            }

            //查找
            public int find(int i) {
                if (parent[i] != i)
                    parent[i] = find(parent[i]);
                return parent[i];
            }

            //合并
            public void union(int x, int y) {
//                System.out.println("=========UNION=====");
//                System.out.println("x:" + x + ",y:" + y);
                //查找两个节点的代表节点
                int rootX = find(x);
                int rootY = find(y);
//                System.out.println("rootX:" + rootX + ",rootY:" + rootY);
                //如果不属于同一个集合，进行合并
                if (rootX != rootY) {
                    if (rank[rootX] > rank[rootY]) {
                        parent[rootY] = rootX;
                    } else if (rank[rootX] < rank[rootY]) {
                        parent[rootX] = rootY;
                    } else {
                        parent[rootY] = rootX;
                        rank[rootX] += 1;
                    }
                    --count;
                }
//                System.out.println("parent:" + Arrays.toString(parent));
//                System.out.println("=========UNION=====");

            }

            public int getCount() {
                return count;
            }
        }


        private int dfs(char[][] grid) {
            int gridLen = grid.length;
            if (gridLen == 0) {
                return 0;
            }
            int gridWid = grid[0].length;
            int res = 0;
            for (int i = 0; i < gridLen; i++) {
                for (int j = 0; j < gridWid; j++) {
                    if (grid[i][j] == '1') {
                        res++;
                        dfs(i, j, grid);
                    }
                }
            }
            return res;
        }

        private void dfs(int i, int j, char[][] grid) {
            if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') {
                return;
            }
            grid[i][j] = '0';
            dfs(i + 1, j, grid);
            dfs(i - 1, j, grid);
            dfs(i, j + 1, grid);
            dfs(i, j - 1, grid);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}